Proofs and Computation

Abstract: Proofs have always gone hand in hand with the development of (the theory of) computation. The Turing Machine was conceived to generalize and extend Godel's incompleteness theorem. The P vs. NP question emerged in part out of an effort to understand the complexity of theorem-proving. And modern theories of optimization, cryptography and even aspects of quantum physics are intimately tied to novel notions associated with proofs such interaction and randomness. In this talk we will survey some of these classical connections as well as the more modern ones; and ponder some, as of yet unresolved, enigmas associated with proofs we use in day to day (mathematical) life.

quantum computing and informationMathematicsPhysics

Audience: researchers in the topic

Mathematical Picture Language Seminar